Sử sách không cho biết ngày tháng năm sinh và gia thế của Lương Sùng Nghĩa, chỉ ghi rằng ông là người Trường An[3]. Ông được nhiều người biết đến vì có sức khỏe phi thường, có thể bẻ cong thỏi vàng hay kéo giãn sợi kim loại. Ban đầu, ông được bổ nhiệm làm cung thủ bảo vệ hoàng cung, về sau đi theo tướng Lai Thiến tham gia vào chiến dịch tiêu diệt phản quân An-Sử. Trong thời gian đó, Lương Sùng Nghĩa tỏ ra trầm lặng và ít nói, nhưng được lòng tướng sĩ dưới quyền; về sau dời làm Thiên bì. Khi Lai Thiến được bổ làm Tiết độ sứ Sơn Nam Đông Đạo, đến đóng tại Tương Dương, Lương Sùng Nghĩa cũng đi theo ông ta. Trong thời gian đó, Lai Thiến thường xuyên vào triều yết kiến Đường Túc Tông, phân chư tướng trấn giữ một số nơi; trong đó Lương Sùng Nghĩa được cử đến giữ vùng Nam Dương[3][4]...

Đại Tông lên ngôi (762), hạ lệnh dời Lai Thiến đến trấn giữ đất Hoài Tây nhằm triệt bớt vây cánh của ông ta, Lai Thiến ra sức từ chối và vẫn ở lại trấn. Cuối năm 762, khi hoạn quan Lý Phụ Quốc bị giết, Lai Thiến bị Vương Trọng Thăng tố cáo là khi trước có mưu đồ liên kết với quân Đại Yên, cuối cùng ông ta bị cách chức, lưu đày rồi bị ép phải tự tử.

Lúc bấy giờ Lương Sùng Nghĩa đang ở Nam Dương, nghe được tin đó, đem quân tới Tương châu. Ông cùng các tướng khác là Lý Chiêu và Tiết Nam Dương trở thành những người có khả năng lên thay chức Tiết độ sứ. Quân sĩ ủng hộ ông, nói: Binh không thể không do Lương khanh làm chủ[3]. Rồi tôn Sùng Nghĩa lên nằm quyền chỉ huy. Tháng 2 ÂL năm 763, Sùng Nghĩa giết Chiêu và Nam Dương, đe dọa trừng phạt những ai chống đối. Lúc bấy giờ nhà Đường suy yếu, đành phải công nhận Lương Sùng Nghĩa là Tiết độ sứ ở Sơn Nam Đông Đạo[5].